/*
 * @lc app=leetcode id=93 lang=cpp
 *
 * [93] Restore IP Addresses
 */
class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> ret;
        int len = s.length();
        if (len < 4) {
            return ret;
        }

        vector<string> tokens;
        loop(s, 0, tokens, ret);
        return ret;
    }

    void loop(string& s, int pos, vector<string>& tokens, vector<string>& ret) {

        int len = s.length();
        if (len == pos && tokens.size() == 4) {
            string ip = tokens[0]+'.'+tokens[1]+'.'+tokens[2]+'.'+tokens[3];
            ret.push_back(ip);
            return ;
        }

        if (len < pos || tokens.size() >= 4) {
            return ;
        }

        for (int i=1; i<=3; i++) {
            if (pos + i > len) {
                break;
            }
            string slice = s.substr(pos,i);
            if (validIPSlice(slice)) {
                tokens.push_back(slice);
                loop(s, pos+i, tokens, ret);
                tokens.pop_back();
            }
        }
    }

    bool validIPSlice(string s) {
        int len = s.length();
        if (len == 1) {
            if (isDigit(s[0])) {
                return true;
            }
        } else if (len == 2) {
            if (isDigit(s[0]) && isDigit(s[1]) && s[0] != '0') {
                return true;
            }
        } else if (len == 3) {
            if (isDigit(s[0]) && isDigit(s[1]) && isDigit(s[2])) {
                if (s[0] == '1') {
                    return true;
                } else if (s[0] == '2') {
                    if ((s[1] < '5') || (s[1]=='5' && s[2]<='5')) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    bool isDigit(char c) {
        return c >= '0' && c <= '9';
    }
};

